package Q713

/**
 * 乘积小于K的子数组
 * @author 23737
 * @date 2022.5.5
 */
class Main {

}

fun main() {
    val nums: IntArray = intArrayOf(10, 2, 5, 6)
    val k = 100
    println(Solution().numSubarrayProductLessThanK(nums, k))
}

class Solution {
    fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
        if (k == 0) return 0
        var res = 0
        var max = 1
        var index = 0
        for (i in nums.indices) {
            max *= nums[i]
            while (index <= i && max >= k) {
                max /= nums[index]
                index++
            }
            res += i - index + 1
        }
        return res
    }
}